package priv.pront.code.national.acwing.dp.linear;

import java.io.*;

public class A899_编辑距离 {

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int INF = 0x3f3f3f3f;

    public static int minEdit(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 1; i <= n1; i++) dp[i][0] = i;
        for (int i = 1; i <= n2; i++) dp[0][i] = i;
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                dp[i][j] = INF;
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = Math.min(dp[i][j],
                        dp[i - 1][j - 1] + (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1));
            }
        }
        return dp[n1][n2];
    }

    public static void main(String[] args) throws Exception {
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = read.readLine();
        }
        while (m-- > 0) {
            int ans = 0;
            ss = read.readLine().split(" ");
            int limit = Integer.valueOf(ss[1]);
            for (int i = 0; i < n; i++) {
                if (minEdit(s[i], ss[0]) <= limit) ans++;
            }
            System.out.println(ans);
        }

    }
}
